home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / gnustuff / minix / libsrc~1.z / libsrc~1 / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-12-28  |  6.6 KB  |  263 lines
  1. /*
  2.  * qsort - parts adapted from Doug Schmidt's sort challenge posting
  3.  *       thanks Doug
  4.  *
  5.  *        ++jrb    bammi@dsrgsun.ces.cwru.edu
  6.  */
  7.  
  8. #if (defined(minix) || defined(unix))
  9. #  include <sys/types.h>
  10. #  ifdef minix
  11. #    include "lib.h"
  12. #  endif
  13. #else
  14. #  include <stddef.h>
  15. #  include <stdlib.h>
  16. #endif
  17. #include <string.h>
  18.  
  19. #ifdef __GNUC__
  20. #  ifdef minix
  21.      void *alloca(unsigned long);
  22. #  else
  23. #    define alloca __builtin_alloca
  24. #  endif
  25. #  define INLINE inline
  26. #else
  27. #  define INLINE /* */
  28. #endif
  29.  
  30.     
  31.     /* the next 4 #defines implement a very fast in-line stack abstraction */
  32.     
  33. #define MAKE_STACK(S) \
  34.     ((stack_node *) alloca((unsigned long)(sizeof(stack_node) * (S))))
  35. #define PUSH(LOW,HIGH) \
  36.     top->lo = LOW; top->hi = HIGH; top++
  37. #define POP(LOW,HIGH) \
  38.     --top; LOW = top->lo; HIGH = top->hi
  39. #define STACK_NOT_EMPTY \
  40.     (stack < top)                
  41.  
  42. static void swap(unsigned char *, unsigned char *, size_t);
  43. static void Move(unsigned char *, unsigned char *, size_t);
  44. static void insert_sort(void *, void *, size_t, int (*)());
  45. static void *find_pivot(void *, void *, size_t, int (*)());
  46.  
  47.  
  48.  
  49. /* Discontinue quicksort algorithm when partition gets below this size. */
  50.  
  51. #ifndef MAX_THRESH
  52. #define MAX_THRESH 15
  53. #endif
  54.  
  55. /* Data structure for stack of unfulfilled obligations. */
  56. typedef struct 
  57. {
  58.     void *lo;
  59.     void *hi;
  60. } stack_node;
  61.  
  62. static void *scratch;    /* scratch mem */
  63.  
  64. /* swap two elements of size n each */
  65. INLINE static void swap(a, b, n)
  66. unsigned char *a, *b;
  67. size_t n;
  68. {
  69.     unsigned char t;
  70.     while(n--)
  71.     {
  72.     t    = *a;
  73.         *a++ = *b;
  74.     *b++ = t;
  75.     }
  76. }
  77.  
  78.  
  79. /* move src to dest */
  80. INLINE static void Move(src, dst, n)
  81. unsigned char *src, *dst;
  82. size_t n;
  83. {
  84.     while(n--)
  85.     *dst++ = *src++;
  86. }
  87.  
  88.  
  89. /* Once main array is partially sorted by quicksort the remainder is 
  90.    completely sorted using insertion sort, since this is efficient 
  91.    for partitions below MAX_THRESH size. BASE points to the beginning 
  92.    of the array to sort, and END_PTR points at the very last element in
  93.    the array (*not* one beyond it!). */
  94.  
  95. INLINE static void 
  96.     insert_sort(void *base, void *end_ptr, size_t siz, int (*cmp)())
  97. {
  98.     void *run_ptr;
  99.     void *tmp_ptr = end_ptr;
  100.     void *temp = scratch;
  101.  
  102.     /* Find the largest element in the array and put it at the 
  103.        end of the array.  This acts like a sentinel, and it speeds
  104.        up the inner loop of insertion sort. */
  105.  
  106.     for (run_ptr = end_ptr - siz; run_ptr >= base; run_ptr -= siz)
  107.     if ((*cmp)(run_ptr, tmp_ptr) > 0) 
  108.         tmp_ptr = run_ptr;
  109.  
  110.     if(tmp_ptr != end_ptr)
  111.     { swap (tmp_ptr, end_ptr, siz); }
  112.  
  113.     /* Typical insertion sort, but we run from the `right-hand-side'
  114.        downto the `left-hand-side.' */
  115.     
  116.     for (run_ptr = end_ptr - siz; run_ptr > base; run_ptr -= siz) 
  117.     {
  118.     tmp_ptr = run_ptr - siz;
  119.     Move(tmp_ptr, temp, siz);
  120.  
  121.     /* Select the correct location for the new element, 
  122.        by sliding everyone down by 1 to make room! */
  123.     
  124.     while ((*cmp)(temp , (tmp_ptr += siz)) > 0)
  125.         Move(tmp_ptr, (tmp_ptr - siz), siz);
  126.  
  127.     Move(temp, tmp_ptr - siz, siz);
  128.     }
  129. }
  130.  
  131. /* Return the median value selected from among the 
  132.    LOW, MIDDLE, and HIGH.  Rearrange LOW and HIGH so
  133.    the three values are sorted amongst themselves. 
  134.    This speeds up later work... */
  135.  
  136. INLINE static void *
  137.     find_pivot(void *low, void *high, size_t siz, int (*cmp)())
  138. {
  139.     void *middle = low + (((high - low)/siz) >> 1) * siz;
  140.     
  141.     if ((*cmp)(middle, low) < 0)
  142.     { swap (middle, low, siz); }
  143.     if ((*cmp)(high, middle) < 0)
  144.     { swap (middle, high, siz); }
  145.     else 
  146.     return middle;
  147.     
  148.     if ((*cmp)(middle, low)  < 0)
  149.     { swap (middle, low, siz); }
  150.     
  151.     return middle;
  152. }
  153.  
  154. /* Order elements using quicksort.  This implementation incorporates
  155.    4 optimizations discussed in Sedgewick:
  156.    
  157.    1. Non-recursive, using an explicit stack of log (n) pointers that 
  158.    indicate the next array partition to sort.
  159.    
  160.    2. Choses the pivot element to be the median-of-three, reducing
  161.    the probability of selecting a bad pivot value.
  162.    
  163.    3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
  164.    insertion sort to sort within the partitions.  This is a
  165.    big win, since insertion sort is faster for small, mostly
  166.    sorted array segements.
  167.    
  168.    4. The larger of the 2 sub-partitions are always pushed onto the
  169.    stack first, with the algorithm then concentrating on the
  170.    smaller partition.  This *guarantees* no more than log (n)
  171.    stack size is needed! */
  172.  
  173. void qsort(base, total_elems, size, cmp)
  174. void *base;
  175. size_t total_elems;
  176. size_t size;
  177. int (*cmp)();
  178. {
  179.     if (total_elems > 1)
  180.     {
  181.     void        *lo;
  182.     void        *hi;
  183.     void        *left_ptr;
  184.     void        *right_ptr;
  185.     void        *pivot;
  186.     size_t        Thresh = MAX_THRESH * size;
  187.     stack_node  *stack;
  188.     stack_node  *top;  
  189.     size_t max_stack_size = 1;
  190.  
  191.     /* Calculate the exact stack space required in the worst case.
  192.        This is approximately equal to the log base 2 of TOTAL_ELEMS. */
  193.     
  194.     {   size_t i;    /* this helps the compiler */
  195.         for (i = 1; i < total_elems; i += i) 
  196.             max_stack_size++;
  197.     }
  198.     /* Create the stack, or die trying! */
  199.     if (stack = MAKE_STACK (max_stack_size))
  200.         top = stack;
  201.     else
  202.         return;
  203.  
  204.     /* allocate scratch */
  205.     if((scratch = alloca(size)) == (void *)0)
  206.         return;    /* die */
  207.     
  208.     lo = base;
  209.     hi = lo + (total_elems - 1) * size;
  210.  
  211.     do {
  212.         next: if((hi - lo) <= Thresh)
  213.         {
  214.         insert_sort(lo, hi, size, cmp);
  215.         if(STACK_NOT_EMPTY)
  216.             {  POP(lo, hi); goto next; }
  217.         else
  218.             break;
  219.         }
  220.         /* otherwise next iteration of qsort */
  221.         /* Select the median-of-three here. This allows us to
  222.            skip forward for the LEFT_PTR and RIGHT_PTR. */
  223.         pivot = find_pivot (lo, hi, size, cmp);
  224.         left_ptr  = lo + size;
  225.         right_ptr = hi - size; 
  226.  
  227.         /* Here's the famous ``collapse the walls'' section of
  228.            quicksort.  Gotta like those tight inner loops! */
  229.         do { /* partition loop */
  230.         while ((*cmp)(left_ptr, pivot) <= 0) /* see knuth for <= */
  231.             left_ptr += size;
  232.         
  233.         while ((*cmp)(pivot, right_ptr) <= 0)
  234.             right_ptr -= size;
  235.         
  236.         if (left_ptr < right_ptr) 
  237.                 {
  238.             swap (left_ptr, right_ptr, size);
  239.             left_ptr += size;
  240.             right_ptr -= size;
  241.                 }
  242.         else if (left_ptr == right_ptr) 
  243.                 {
  244.             left_ptr +=size; 
  245.             right_ptr -= size; 
  246.             break;
  247.                 }
  248.             } while (left_ptr <= right_ptr);
  249.         
  250.         if ((right_ptr - lo) > (hi - left_ptr)) 
  251.             {                   /* push larger left table */
  252.         PUSH (lo, right_ptr);
  253.         lo = left_ptr;
  254.             }
  255.         else 
  256.             {                   /* push larger right table */
  257.         PUSH (left_ptr, hi);
  258.         hi = right_ptr;
  259.             }
  260.         } while(1);    /* when stack is empty it'll break out */
  261.     } /* if total_elems > 1 */
  262. }
  263.